1. Field of the Invention
The present invention relates to storing and retrieving still images from large digital still image archives when the still images are encoded using the JPEG (Joint Photographic Experts Group) encoding standard, and specifically to the extraction, based on the coefficients of the Discrete Cosine Transforms, of still image index keys from JPEG encoded still images, and to the search for and retrieval of still images based on the extracted index keys.
2. Description of the Related Art
Managing large collections of images was once only a problem for specialists in fields such as remote sensing, intelligence-gathering, and medical imaging. With the growth of multimedia computing and the spread of the INTERNET, an increasing number of people can display and manipulate images, and use them for a variety of applications.
JPEG is an encoding standard used for digitally encoding, typically with a computer, still images for use in the information processing industry. With the JPEG encoding standard, still images can be stored on CD-ROMs, magnetic storage such as hard drives, diskettes, and tape. Further, the JPEG encoding standard allows still images to be transmitted through computer networks such as ISDN, wide area networks, local area networks, the INTERNET, the INTRANET and other communication channels.
The JPEG standard for compressing images is mostly used as a lossy compression scheme. JPEG can also be configured as a lossless method. The JPEG compression standard is described in "The JPEG Still Picture Compression Standard", by Gregory T. Wallace, Communications of the ACM, April 1991, vol. 34, No. 4, pp. 31-44, incorporated by reference herein.
JPEG uses a combination of spatial-domain and frequency-domain coding. For grayscale images, the image is first divided into 8.times.8 pixel blocks, each of which is transformed into the frequency domain using the Discrete Cosine Transform (DCT). Each block of the image is thus represented by 64 frequency components. The signal carrying the JPEG-encoded image tends to concentrate in lower spatial frequencies, enabling high-frequency components (many of which are usually zero) to be discarded without substantially affecting appearance of the image.
A main source of loss of information in JPEG-encoded images is a quantization of the DCT coefficients. A table of quantization coefficients is used, one per coefficient, usually related to human perception of the different frequencies. The quantized coefficients are ordered in a "zig-zag" sequence by the JPEG compression scheme, starting at the upper left (which is the DC coefficient), and scanning the matrix of coefficients diagonally, since most of the energy lies in the first few coefficients. As a result, most non-zero values appear early in the sequence of coefficient values.
The final step is entropy coding of the coefficients, using either Huffman coding or arithmetic coding.
With the JPEG encoding standard, color image compression can be approximated by compression of multiple grayscale images. In the JPEG encoding standard, color representation is YCrCb, a color scheme in which the luminance component and chrominance components are separated. Y is a luminance component of color, and CrCb are two components of chrominance of color. For each four pixels of luminance, one pixel of Cr and one pixel of Cb is present. In the JPEG encoding standard, the chrominance information is subsampled at one-half of a luminance rate in both the horizontal and vertical directions, giving one value of Cr and one value of Cb for each 2.times.2 block of luminance pixels. Chrominance and luminance pixels are organized into 8.times.8 pixel blocks (or blocks). Pixel blocks are transformed into the frequency domain using the DCT operation, resulting in DC and AC components corresponding to the pixel blocks.
A macro block comprises four 8.times.8 blocks of luminance pixels and one 8.times.8 block for each of two chrominance (chroma) components. Therefore, a macroblock comprises the DCT coefficients for four 8.times.8 blocks of luminance pixels and one 8.times.8 block for each of two chrominance coefficient pixels.
A problem in the related art is that most image databases are not indexed in useful ways, and many are not indexed at all. Creating an index of images, then, is a formidable task using technology of the related art.